package com.example.system.class12;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Date 2022/7/31
 * @Author Jonathan
 * @Description 二叉树的最大宽度
 */
public class Code02_BTMaxWidth {

    private static int index = 0;

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1, 8, 12, null, null, null, 4, 3, null, null, 9, null, null};
        final Node root = createBST(arr);
        System.out.println(maxWidth(root));

    }


    public static int maxWidth(Node root) {
        // 借助队列
        Queue<Node> queue = new LinkedList<>();
        Node nextLevelLast = null;
        Node curLevelLast = root;
        queue.add(root);
        int max = 0;
        int curLevelWidth = 0;
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            curLevelWidth++; //宽度加一
            if (node.left != null) {
                queue.add(node.left);
                nextLevelLast = node.left;
            }

            if (node.right != null) {
                queue.add(node.right);
                nextLevelLast = node.right;
            }

            if (node == curLevelLast) {
                max = Math.max(max, curLevelWidth);
                curLevelLast = nextLevelLast;       // 更新当前层的最后一个节点
                curLevelWidth = 0;                  // 初始化当层的节点数 方便下一轮计数
            }
        }
        return max;
    }


    static class Node {
        Node left;
        Node right;
        int value;

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node[" +
                    "value=" + value +
                    ']';
        }
    }


    public static Node createBST(Integer[] arr) {
        if (arr == null || arr.length <= 0) {
            return null;
        }
        return create(arr);
    }

    // 借助全局变量实现
    public static Node create(Integer[] arr) {
        Integer value = arr[index++];
        if (value == null) {
            return null;
        }
        final Node node = new Node(value);
        node.left = create(arr);
        node.right = create(arr);
        return node;
    }

}
